package com.leetBook.Krahets.array;

import org.junit.Test;

import java.util.ArrayList;

/**
 * 《图解算法与数据结构》数组第 4 题：设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。
 * 提示：
 * <p>
 * 0 ≤ documents[i] ≤ n-1
 * 2 <= n <= 100000
 */
public class RepeatNode {
    @Test
    public void fun1(){
        int[] ints = {0, 5, 3, 2, 5, 3};
        System.out.println(findRepeatDocument(ints));;
    }

    /**
     * 官方解答，使用交换的方式
     * @param documents 数组
     * @return 其中一个重复值
     */
    public int findRepeatDocument(int[] documents) {
        int i = 0;
        while (i < documents.length) {
            if (documents[i] == i) {
                i++;
                continue;
            }
            if (documents[documents[i]] == documents[i]) return documents[i];
            int tmp = documents[i];
            documents[i] = documents[tmp];
            documents[tmp] = tmp;
        }
        return -1;
    }

    public int findRepeatDocumentMy(int[] documents) {
        if (documents == null) return -1;

        Integer[] ints = new Integer[documents.length];

        for (int i = 0; i < documents.length; i++) {
            if (ints[documents[i]] != null) {
                return documents[i];
            } else {
                ints[documents[i]] = documents[i];
            }
        }

        return -1;
    }
}
